#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: find_median.py 
@version:
@time: 2024/01/22 
"""

# 方法一
import math

"""
假设两个数组的长度分别为m和n，第一种方法是最简单直接的，另外开辟一块m+n大小的空间，
将两个数组合二为一重新排序，然后根据合并后的数组取中位数就十分简单了

时间复杂度为O((n+m)log(m+n))
空间复杂度为O(n+m)
"""


def find_median(nums1, nums2):
    nums3 = nums1 + nums2
    nums3.sort()
    return (nums3[len(nums3) // 2] + nums3[(len(nums3) - 1) // 2]) / 2


print(find_median([1, 5], [3]))
# 方法二
"""
利用双指针将两个数组排序
"""


def find_median2(nums1, nums2):
    nums3 = []
    j = i = 0

    while i < len(nums1) and j < len(nums2):
        if nums1[i] < nums2[j]:
            nums3.append(nums1[i])
            i += 1
        else:
            nums3.append(nums2[j])
            j += 1
        if i == len(nums1) and j != len(nums2):
            nums3.append(nums2[j:])
        if j == len(nums2) and i != len(nums1):
            nums3.append(nums1[i:])
    return (nums3[len(nums3) // 2] + nums3[(len(nums3) - 1) // 2]) / 2


print(find_median2([1, 5], [3]))

# 方法三
"""
首先考虑采用二分法，然后对二分后的数组进行分治处理

分别找到两个数组array1和array2的中位数，分别为median1和median2，

若median1小于median2，那么median1左侧的所有元素均小于它，

这些元素不可能是中位数，可以截去头部到median2之前的所有元素，长度为p2；

而median2右侧的所有元素均大于它，越接近尾部元素越大，也不能是中位数，截去尾部长度为p2的部分；

然后对着两个数组被截去后剩余部分执行同样操作。

1. 编写获取中位数公共函数
2. 规定array1为短数组，array2为长数组
3. 需要判断输入的两个数组中较短的一个长度是否已经小于等于2，若是，则可以停止递归调用，直接对剩余部分寻找中位数。
为了进一步降低时间复杂度，若较长数组的长度大于4，则对其做截断，取其中心部分，即中位数前后的3-4位，取3位还是4位与较长数组长度是奇数还是偶数有关。

关于对较长数组截取3位还是4位，对偶数长度的数组而言，截取4位为中间部分，对奇数长度的数组而言，截取3位为中间部分。

1. 当较长数组长度为奇数5时，Array=[1,2,3,4,5],那么math.ceil(len2/2)为3，指向数字4，那么Array[1:-1]=[2,3,4]，是数组的中心部分，其中包含数组的中位数。
2. 当较长数组长度为偶数时，Array=[1,2,3,4,5,6],那么math.ceil(len2/2)为3，也指向数字4，那么取Array[1:-1]=[2,3,4,5]，是数组的中心部分，其中位数由3和4求平均得到，
因此截取部分也包含其中位数的两个部分。

将截取的两个部分合并排序取中位数

当短数组array1的中位数较小时，array1中位数之前的所有元素就被截去，对array2的尾部截取相同长度，然后对两个数组递归调用。

当短数组array2的中位数较小时，array2中位数之前的所有元素就被截去，对array1的尾部截取相同长度，然后对两个数组递归调用。

"""


def find_median3(array1, array2):
    len1 = len(array1)
    len2 = len(array2)
    if len1 > len2:
        return find_median3(array2, array1)

    if len1 <= 2:
        if len2 > 4:
            p1 = math.ceil(len2 / 2) - 2
            array2 = array2[p1:-p1]
        nums = array1 + array2
        nums.sort()
        return get_median_num(nums)

    p2 = math.ceil(len1 / 2) - 1
    if get_median_num(array1) < get_median_num(array2):
        return find_median3(array1[p2:], array2[:-p2])
    else:
        return find_median3(array1[:-p2], array2[p2:])


def get_median_num(nums):
    return (nums[len(nums) // 2] + nums[(len(nums) - 1) // 2]) / 2


print(find_median3([1, 5], [3]))
